package Demo01;

import sun.awt.util.IdentityLinkedList;

import java.util.*;


public class Test {
    public static void main(String[] args) {
        MyCircularDeque myCircularDeque = new MyCircularDeque(77);
        myCircularDeque.insertFront(89);
        myCircularDeque.deleteLast();
        myCircularDeque.insertFront(19);
        myCircularDeque.insertFront(23);
        myCircularDeque.insertFront(23);
        myCircularDeque.insertFront(82);
        myCircularDeque.insertFront(45);
        myCircularDeque.deleteLast();
        myCircularDeque.insertLast(74);
        myCircularDeque.deleteFront();
//        myCircularDeque.insertLast(1);
//        myCircularDeque.insertLast(2);
//        myCircularDeque.insertFront(3);
//        myCircularDeque.insertFront(4);
//        System.out.println(myCircularDeque.getFront());

    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()) {
            if (cur.left == null && cur.right == null) {
                list.add(cur.val);
                stack.pop();
            } else if (cur.left != null) {
                stack.push(cur.left);
            } else if (cur.right != null) {
                stack.push(cur.right);
            }
        }

        return list;
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur == null) {
                cur = stack.pop().right;
            } else {
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
        }

        return list;
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur == null) {
                TreeNode tmpNode = stack.pop();
                list.add(tmpNode.val);
                cur = tmpNode.right;
            } else {
                stack.push(cur);
                cur = cur.left;
            }
        }
        return list;
    }
}

class MyCircularDeque {
    int[] arr;
    int begin;
    int end;
    int count;
    int limit;

    public MyCircularDeque(int k) {
        arr = new int[k];
        begin = k - 1;
        end = 0;
        //数组元素个数
        count = 0;
        //数组最大容量
        limit = k;
    }

    public boolean insertFront(int value) {
        if (count == limit) {
            return false;
        }
        arr[begin] = value;
        if (begin == 0) {
            begin = arr.length - 1;
        } else {
            begin--;
        }
        count++;
        return true;
    }

    public boolean insertLast(int value) {
        if (count == limit) {
            return false;
        }
        arr[end] = value;
        if (end == limit - 1) {
            end = 0;
        } else {
            end++;
        }
        count++;
        return true;
    }

    public boolean deleteFront() {
        if (count == 0) {
            return false;
        }
        if (begin == limit - 1) {
            begin = 0;
        } else {
            begin++;
        }
        count--;
        return true;
    }

    public boolean deleteLast() {
        if (count == 0) {
            return false;
        }
        if (end == 0) {
            end = limit - 1;
        } else {
            end--;
        }
        count--;
        return true;
    }

    public int getFront() {
        if (count == 0) {
            return -1;
        }
        if (begin == limit - 1) {
            return arr[0];
        } else {
            return arr[begin + 1];
        }
    }

    public int getRear() {
        if (count == 0) {
            return -1;
        }
        if (end == 0) {
            return arr[limit - 1];
        } else {
            return arr[end - 1];
        }
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public boolean isFull() {
        return limit == count;
    }
}


class MinStack {
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();

    public MinStack() {
    }

    public void push(int val) {
        if (stack.isEmpty()) {
            stack.push(val);
            minStack.push(val);
        } else {
            stack.push(val);
            if (val <= minStack.peek()) {
                minStack.push(val);
            }
        }
    }

    public void pop() {
        int res = stack.pop();
        if (res == minStack.peek()) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}


/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque obj = new MyCircularDeque(k);
 * boolean param_1 = obj.insertFront(value);
 * boolean param_2 = obj.insertLast(value);
 * boolean param_3 = obj.deleteFront();
 * boolean param_4 = obj.deleteLast();
 * int param_5 = obj.getFront();
 * int param_6 = obj.getRear();
 * boolean param_7 = obj.isEmpty();
 * boolean param_8 = obj.isFull();
 * <p>
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque obj = new MyCircularDeque(k);
 * boolean param_1 = obj.insertFront(value);
 * boolean param_2 = obj.insertLast(value);
 * boolean param_3 = obj.deleteFront();
 * boolean param_4 = obj.deleteLast();
 * int param_5 = obj.getFront();
 * int param_6 = obj.getRear();
 * boolean param_7 = obj.isEmpty();
 * boolean param_8 = obj.isFull();
 * <p>
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque obj = new MyCircularDeque(k);
 * boolean param_1 = obj.insertFront(value);
 * boolean param_2 = obj.insertLast(value);
 * boolean param_3 = obj.deleteFront();
 * boolean param_4 = obj.deleteLast();
 * int param_5 = obj.getFront();
 * int param_6 = obj.getRear();
 * boolean param_7 = obj.isEmpty();
 * boolean param_8 = obj.isFull();
 * <p>
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque obj = new MyCircularDeque(k);
 * boolean param_1 = obj.insertFront(value);
 * boolean param_2 = obj.insertLast(value);
 * boolean param_3 = obj.deleteFront();
 * boolean param_4 = obj.deleteLast();
 * int param_5 = obj.getFront();
 * int param_6 = obj.getRear();
 * boolean param_7 = obj.isEmpty();
 * boolean param_8 = obj.isFull();
 * <p>
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque obj = new MyCircularDeque(k);
 * boolean param_1 = obj.insertFront(value);
 * boolean param_2 = obj.insertLast(value);
 * boolean param_3 = obj.deleteFront();
 * boolean param_4 = obj.deleteLast();
 * int param_5 = obj.getFront();
 * int param_6 = obj.getRear();
 * boolean param_7 = obj.isEmpty();
 * boolean param_8 = obj.isFull();
 * <p>
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque obj = new MyCircularDeque(k);
 * boolean param_1 = obj.insertFront(value);
 * boolean param_2 = obj.insertLast(value);
 * boolean param_3 = obj.deleteFront();
 * boolean param_4 = obj.deleteLast();
 * int param_5 = obj.getFront();
 * int param_6 = obj.getRear();
 * boolean param_7 = obj.isEmpty();
 * boolean param_8 = obj.isFull();
 */


/*class MyCircularDeque {
    int size;
    int limit;
    int front;
    int tail;
    int[] arr;
    public MyCircularDeque(int k) {
        arr = new int[k];
        size = 0;
        limit = k;
        front = 0;
        tail = 0;
    }

    public boolean insertFront(int value) {
        if(arr.length==0||size==limit) {
            return false;
        }

        if(front==0&&tail!=front) {
            front = limit-1;
            arr[front] = value;
            size++;
            return true;
        }
        if (front==0&&tail==front) {
            arr[front] = value;
            front = limit-1;
            size++;
            return true;
        }
        arr[front] = value;
        front--;
        size++;
        return true;
    }
    public boolean deleteFront() {
        if(size==0) {
            return false;
        }
        if(front==limit-1) {
            front = 0;
            size--;

        }else {
            front++;
            size--;
        }
        return true;
    }

    public boolean insertLast(int value) {
        if(arr.length==0||limit==size) {
            return false;
        }
        if(tail==limit-1) {
            arr[tail] = value;
            tail = 0;
            size++;
        }else {
            arr[tail] = value;
            tail++;
            size++;
        }
        return true;
    }


    public boolean deleteLast() {
        if(size==0) {
            return false;
        }
        if(tail==0) {
            tail = limit-1;
            size--;
        }else {
            tail--;
            size--;
        }
        return true;
    }

    public int getFront() {
        return arr[front];
    }

    public int getRear() {
        return arr[tail];
    }

    public boolean isEmpty() {
        return size==0;
    }

    public boolean isFull() {
        return size==limit;
    }
}*/

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque obj = new MyCircularDeque(k);
 * boolean param_1 = obj.insertFront(value);
 * boolean param_2 = obj.insertLast(value);
 * boolean param_3 = obj.deleteFront();
 * boolean param_4 = obj.deleteLast();
 * int param_5 = obj.getFront();
 * int param_6 = obj.getRear();
 * boolean param_7 = obj.isEmpty();
 * boolean param_8 = obj.isFull();
 */

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */
class MyStack {
    Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();
    }

    public void push(int x) {
        if (queue.isEmpty()) {
            queue.offer(x);
        } else {
            int size = queue.size();
            queue.offer(x);
            while (size-- == 1) {
                queue.offer(queue.poll());
            }
        }
    }

    public int pop() {
        return queue.poll();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}


class MyStack1 {
    Queue<Integer> queue1;
    Queue<Integer> queue2;

    public MyStack1() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        if (!queue1.isEmpty()) {
            queue1.offer(x);
        } else {
            queue2.offer(x);
        }
    }

    public int pop() {
        if (queue1.isEmpty()) {
            if (queue2.isEmpty()) {
                return 0;
            } else {
                int size = queue2.size();
                while (size-- != 1) {
                    queue1.offer(queue2.poll());
                }
                return queue2.poll();
            }
        } else {
            if (queue1.isEmpty()) {
                return 0;
            } else {
                int size = queue1.size();
                while (size-- != 1) {
                    queue2.offer(queue1.poll());
                }
                return queue1.poll();
            }
        }
    }

    public int top() {
        if (queue1.isEmpty()) {
            if (queue2.isEmpty()) {
                return 0;
            } else {
                int size = queue2.size();
                while (size-- != 1) {
                    queue1.offer(queue2.poll());
                }
                int res = queue2.peek();
                queue1.offer(queue2.poll());
                return res;
            }
        } else {
            if (queue1.isEmpty()) {
                return 0;
            } else {
                int size = queue1.size();
                while (size-- != 1) {
                    queue2.offer(queue1.poll());
                }
                int res = queue1.peek();
                queue2.offer(queue1.poll());
                return queue1.peek();
            }
        }
    }

    public boolean empty() {
        return queue2.isEmpty() && queue1.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

class MyQueue {
    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();

    public MyQueue() {
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        if (stack2.empty()) {
            if (stack1.empty()) {
                return 0;
            } else {
                int len = stack1.size();
                while (len-- != 0) {
                    stack2.push(stack1.pop());
                }
                return stack2.pop();
            }
        } else {
            return stack2.pop();
        }
    }

    public int peek() {
        if (stack2.isEmpty()) {
            if (stack1.empty()) {
                return 0;
            } else {
                int len = stack1.size();
                while (len-- != 0) {
                    stack2.push(stack1.pop());
                }
                return stack2.peek();
            }
        } else {
            return stack2.peek();
        }
    }

    public boolean empty() {
        return stack1.empty() && stack2.empty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */